Permutations, combinations, bijective proofs, generating functions
3
votes
1answer
52 views
A numeral system built around Dirichlet series, by analogy of how positional numeral systems are built around power series?
For any natural number and chosen base p, the number admits a unique expression of the form $a_np^n + ... + a_2p^2 + a_1p^1 + a_0$, where $a_k < p$ for all k. This property is effectively what ...
7
votes
2answers
179 views
maximum number of edges to be removed to possess a property
I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
0
votes
0answers
15 views
How will an orthogonal array look for 3 levels and 3 factors?
I understand that an orthogonal array with 3 factors (parameters) will have 3 columns and if there are 3 levels, then it means each parameter can have 3 values.
However, when using a selector from ...
1
vote
0answers
20 views
Choosing at random with Replacement. pmf? E(x)?
There are $30$ balls in a box. $6$ of them are red, $10$ are white and $14$ are blue. $10$ balls are chosen at random with replacement.
Let $X$ be the the number of red balls in the sample.
1) ...
2
votes
1answer
32 views
Unable to get to standard permutations after $n-1$ transpositions
Problem: Give an example of a permutation of the first $n$ natural numbers from which it is impossible to get to the standard permutation $1,2,\ldots,n$ after less than $n-1$ transposition operations ...
1
vote
2answers
36 views
How to do a combinatorial proof
I have a question which asked for a combinatorial proof. I have no clue how to do do a combinatorial proof.
The question is
prove that the total number of subsets in $\{x_1, x_2, x_3, ... ,x_n\}$ is ...
2
votes
1answer
75 views
Counting permutation problem
Suppose you have $n$ boxes, each with a ball inside. If you randomly change the place of the balls such that afterwards, there is still a single ball in each box, what is the probability that ...
2
votes
2answers
65 views
Ordinals closed under functions
Let $ \{ f_n : n \in \mathbb N \} $ be a set of functions $f : (\omega_1)^k\to \omega_1 $ where the $k$ is different between functions. Prove that the set of ordinals $\alpha < \omega _1 $ that ...
1
vote
2answers
44 views
Tree, no uncountable antichains
Show that if a $\omega_1$ tree (that is, each vertex has height less than $\omega_1$ and each level $\alpha < \omega_1$ is countable and non-empty) has no uncountable anti chains, and in addition ...
0
votes
0answers
16 views
Equality in a discrete isoperimetric inequality
For a subset $A \subset \mathcal{P}(\{1,...,n\})$ I have seen the following bound on the edge boundary:
$|\partial A| \ge |A|(n-\log_2|A|)$
there is certainly equality whenever $A$ is a "subcube" of ...
1
vote
2answers
37 views
Could graph theory aid in the understanding of comparison sorting algorithms?
I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article.
Up to $n=15$, we know how many comparisons between elements one must make to ...
3
votes
1answer
38 views
Proving that $n|m\implies f_n|f_m$
Question: Let $m,n\in\mathbb{N}$, prove that if $n|m$, $F_n|F_m$.
I've tried to use induction, but I don't really know where to start since there's $2$ numbers: $n$ and $m\ \dots$ I did induction ...
3
votes
1answer
130 views
diameter and radius of a regular graph
I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
2
votes
1answer
22 views
A Permutation problem with sum restrictions
In how many permutations of digits 1, 2, 3,...,9 are the following two conditions satisfied:
Sum of digits between 1 and 2 (including both) is 12.
Sum of digits between 2 and 3 (including both) is ...
1
vote
1answer
34 views
Card Counting in different ways
To answer the following task I can think of two different approaches yet they produce different results. My question is :
which way is the right one and why are they different ?
Task : From a ...
1
vote
1answer
25 views
Answering a bijective counting question
I have a question which I am not sure how to write out. This is my following approach and if it is not right could you tell me a better way to answer this question?
Question:
In how many ways can $k$ ...
4
votes
0answers
25 views
Isomorphism between $E_8$ lattice and lattice defined by Extended Hamming Code
I have read that the following two lattices are isomorphic, and of course it seems believable, but it would be nice to have a sketch of how to construct the bijection.
Let $C$ be some extended ...
2
votes
1answer
30 views
Number of circular combinations with no adjacent members.
Suppose I have to place 3 identical letters on a circular table which has 7 slots in such a way that no two letters are in consecutive slots. In how many ways can I do this?
Can this be generalized ...
2
votes
2answers
40 views
Counting problem: Assigning students to dorm rooms
This was a question on a recent test and I was hoping for a conclusive answer and reasoning behind it.
A local university housing office has a problem. It has 11 students to squeeze into 3 dorm ...
2
votes
1answer
46 views
Unique sequences from different sets
I am given $n$ sets with a selection of $m$ elements, such as:
$$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$
I am trying to calculate the number of unique sequences that contain all elements ...
0
votes
2answers
41 views
Combinations of letters
I have been struggling the last hour on the following statement to workout out which method to use and and why that method gets used. Please keep the term simple because I am not a math genius.
...
2
votes
2answers
41 views
Number of rectangles with odd side lengths on a chess board?
Given an 8x8 chess board, how do we find the total number of rectangles with odd side lengths?
(Both sides have odd length).
In general, what would be an elegant method to deal with problems like ...
4
votes
2answers
101 views
A classical problem in combinatorics/probability
I read this problem in Cognition and Chance by Raymond Nickerson (the problem is stated not discussed)
...
2
votes
0answers
101 views
Can a linear combination of even Legendre polynomials have common real root(s) with a linear combination of odd Legendre polynomials?
I am using the following definition of Legendre Polynomials: $P_0(x)=1$, $P_1(x)=x$ and
$$P_{k+1}(x)=\left(\frac{2k+1}{k+1}\right)xP_k(x)−\left(\frac{k}{k+1}\right)P_{k−1}(x)$$
Let
...
2
votes
1answer
69 views
A combinatorial identity
Let $m$ be a positive integer. I have trouble proving that
$$\sum_{k=0}^m (-1)^k 2^{2k-1}\left[{m+k-1\choose 2k}+{m+k\choose 2k}\right]=(-1)^m$$
Anyone?
2
votes
3answers
57 views
Count the number of selecting 5 numbers
I would appreciate if somebody could help me with the following problem:
Q: Count the number of selecting 5 numbers in
$\{1, 2, 3, ... n\} (n>5)$, excepting the choice of consecutive three ...
2
votes
2answers
75 views
Pascal's triangle and combinatorial proofs
This recent question got me thinking, if a textbook (or an exam) tells a student to give a combinatorial proof of something involving (sums of) binomial coefficients, would it be enough to show that ...
2
votes
3answers
105 views
combinatorial argument and by induction proof
Let n be a fixed natural number. Show that:
$$\sum_{r=0}^m \binom {n+r-1}r = \binom {n+m}{m}$$
(A): using a combinatorial argument and (B): by induction on $m$?
-3
votes
0answers
35 views
With a regular set of playing cards (52, 13 of each suit), how many hands of 7 cards with, at least, one sequence of four cards are there? [closed]
With a regular set of playing cards (52, 13 of each suit), how many hands of 7 cards with, at least, one sequence of four cards are there?
OBS: the sequence here is four cards of consecutive values ...
0
votes
1answer
42 views
Counting Methods: Restricted Permutations
I have been scratching my head for a long time. The question is: How many words can be formed using all letters in the word EXAMINATION in such a way that the first two letters are different ...
1
vote
1answer
45 views
Divisibility problem.
In line written squares of natural numbers from 1 to 2012. How many of these numbers have a remainder when divided by 17, which is divisible by 3?
1
vote
2answers
49 views
Monotonic Lattice Paths and Catalan numbers
Can someone give me a cleaner and better explained proof that the number of monotonic paths in an $n\times n$ lattice is given by ${2n\choose n} - {2n\choose n+1}$ than Wikipedia
I do not understand ...
0
votes
0answers
41 views
How to count pairs and their combinations? [closed]
I am trynig to understand that in context of pairwise testing.
From one example, the authors mention that 75 binary options (2^75) can be pair-checked with only 28 combinations.
Or 81 (3^4) in 9.
...
-1
votes
2answers
64 views
Young tableaux of shape lambda.
Consider the partition $\lambda=(m,n-m)$ of $n$ (thus $2m \ge n$.)
The number of Young
tableaux of shape $\lambda$ is given by
$$f_{(m,n-m)} = \binom nm - \binom{n}{m+1}$$
a) Prove this using the ...
3
votes
1answer
48 views
Odd numbers as a sum in Generating Functions
In combinatorics, I have to find (with the help of generating functions) in how many ways I can choose odd numbers from the numbers $[3..15]$ such that adding the numbers will give me $n$
So I said:
...
3
votes
2answers
37 views
Identity of binomial series with factorial.
I'm looking for a simple identity for the formula:
$$
\sum_{k = 0}^{p} \binom{p}{k} \cdot k! \cdot x^k
$$
In words, I have $p$ "players" who can choose to play or not (every player is represented by ...
1
vote
2answers
67 views
Why do we substitute $\alpha^n$ in the recurrences of the form $ax_n=bx_{n-1}+cx_{n-2}$?
I encountered the following recurrence relation $2x_n-3x_{n-1}+x_{n-2}=0$ with $x_0=1$ $x_1=1$.I did not have any idea how to go about this.However, google pointed me to page 18 of Herbert Wilf's ...
0
votes
1answer
61 views
What is the value of this loop counter
Came across this question but unable to solve. What will be the value of the variable "counter"
int counter = 0;
for (int loop_1=0; loop_1 < 10; loop_1++) {
for (int loop_2=loop_1 + 1; loop_2 < ...
1
vote
1answer
31 views
Generating functions of partition numbers
I don't understand at all why:
\begin{equation}
\sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1}
\end{equation}
Where $p_n$ is the number of partitions of $n$. Specifically ...
0
votes
1answer
47 views
Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item
I have the following problem of which I am attempting to find a near optimal solution:
I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
0
votes
0answers
19 views
Computing a restriction of a representation
It is known (Fulton and Harris p.427 among other papers) that the restriction of $\mathrm{GL}_n$ to $\mathrm{O}_n$ yields the following branching rule
$$
...
1
vote
1answer
27 views
Find the probability of having 3 cards of the same suit and 2 cards of the same suit in a 5 card hand from a standard 52 card deck? (Method)
I'm trying to understand why my method doesn't work to answer the question: What is the probability of having 3 cards of the same suit and 2 cards of the same suit (but a different suit than the first ...
0
votes
2answers
32 views
Solving recurrence equations with the help of Generating Functions
I need to solve this recurrence equation with the help of Generating Functions in Combinatorics.
Given:
$$f(0) = 0 , f(1) = 1, f(n) = 10f(n-1) - 25f(n-2) \forall n \geq 2$$
So I said the following:
...
4
votes
1answer
71 views
Counting binary operations on a set with $n$ elements
I am trying to solve following problem but not able to find any way to proceed.
Let $S$ be a set having $n$ elements. Can we count about number of binary operations that can be defined on a set? Can ...
0
votes
2answers
46 views
How many ways are there to encode the 26-letter English Alphabet into 8-bit binary words?
I know that I need 5 bits to represent a character. All the combinations to encode the 26-letter alphabet will be 2^5? How about the 3 bits that remains from 8 bits?
4
votes
0answers
43 views
Hopf Algebras in Combinatorics
I know that many examples of Hopf algebras that come from combinatorics. But I'm interested in knowing how Hopf algebras are applied in solving combinatorial problem.
Are there examples of open ...
0
votes
2answers
53 views
Solving this recursive equations
I have these recursive equations in Combinatorics and I need to find $a_n$
\begin{align}
a_n & = 2b_{n-1} + 2c_{n-1} \\
b_n & = a_{n-1} + c_{n-1} \\
c_n & = a_{n-1} + c_{n-1} + b_{n-1}
...
1
vote
0answers
24 views
Notation for Restriction of Permutation
Suppose $\sigma$ and $\tau$ are permutations such that $\sigma(x)\not=x\implies \sigma(x)=\tau(x)$. Intuitively, I would like to think of $\sigma$ as a restriction (or projection) of $\tau$ onto a ...
0
votes
1answer
13 views
finding out team number
A supervisor has to select a three-member project team from among her 12 employees. Unfortunately, two of the employees cannot work together on the same team. With this restriction, how many different ...
1
vote
1answer
12 views
Pairwise balanced designs
Let $X$ be a finite set containing $v$ elements and $\lambda$ be a positive integer. Let $K$ be a set of positive integers. Further let there be a multiset $\mathcal{B}$ containing subsets of $X$ ...
