This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (5)

0
votes
4answers
45 views

Simple Combination Help! [closed]

Alright, I'm trying to do a simple combination but seem to forget the shortcut. It is (c(6,2)+c(4,2)) over c(10,2). Now finding the answer on my calculator is easy, the problem is that I need to know ...
1
vote
0answers
11 views

How to generate list of values that sum to X given n spots where each value is unique.

For example: Given 2 spots and sum 3 the list would be {1,2} Given 2 spots and sum 4 list would be {1,3} does not contain 2 as putting 2 in both spots violates the uniqueness of each value.
5
votes
1answer
64 views

Toss a fair die until the cumulative sum is a perfect square-Expected Value

Suppose we keep tossing a fair dice until we want to stop, at which point the game ends and our score is the cumulative sum, or until the cumulative sum is a perfect square, in which case we lose and ...
0
votes
1answer
45 views

Proof involving k-permutations

For any nonnegative integers k and m satisfying $0 ≤ k ≤ m$, prove that the total number of $k$-permutations of a set of m elements is $\frac{m!}{(m − k)!}$. I have learned about by proofs by strong ...
1
vote
0answers
24 views

Time for all ants to traverse cube

Let $n$ be a positive integer, and consider a hypercube of dimension $2n$ with $2^{2n}$ points given by $(a_1,a_2,\ldots,a_{2n})$, where $a_i\in\{0,1\}$. At the beginning, an ant is at each of the ...
1
vote
0answers
25 views

the probability of existence sequence [on hold]

We have n fruit that they are apple or banana. If the probability of existence apple in a specific sequence be p. What is the probability of existence a sequence of k apple in that specific sequence?
1
vote
1answer
26 views

How to generate a single instance of multichoose (stars and bars)

So we know that if I have $k$ balls and $n$ buckets, I have $\binom{n+k-1}{k}$ unique ways to allocate the balls. Let's say $n=4$ and $k=2$ then I have $\binom{5}{2}=10$ ways. All possible allocations ...
-1
votes
1answer
23 views

tasks with balls and buckets

We have p identical balls and buckets. We want to know how many ways we can deploy in these buckets. Is my solution good? Why not, why yes (please confirm)? $$ \frac {w ^ p} {p!}$$ For each ball ...
0
votes
1answer
87 views

Probability in DNA segmentation

I have formulated these questions ss part of a research in medical science (DNA segmentation): A series of $M$ identical balls is arranged on a line. A partition is formed by placing a stick to ...
-5
votes
1answer
121 views

Pixel Permutations

How many possible arrangements of pixels can a 1024x768 pixel screen display if the color of a pixel is determined by mixing 3 values: red, green, and blue, ranging from an intensity of 0 to 255? The ...
4
votes
1answer
61 views

How many integers could be in such a way that any digits is not bigger than the left digits?

How many 4-digits integers could be in such a way that any digits is not bigger than it's left digits? I Try it with simulation, i get 714. anyone could describe a formula for me? My try:
1
vote
0answers
35 views
+50

Aumann-Shapley Uniformly Better Principle

Let $n_1,..,n_r$ be $r$ positive integers, and let $1 \leq k \leq n$, where $n=n_1+...+n_r$. Consider an urn containing $r$ different types of balls, $n_1$ balls of type 1, $n_2$ balls of type ...
0
votes
0answers
14 views

Number of ways to transform bit string of length k with j ones

Suppose we can transform any bit string $s$ of length $k$ with $j$ 1s by moving every 1 in $s$ by at most $d$ positions to the right. The resulting string $s'$ is a string of length $k+d$ where every ...
0
votes
2answers
52 views

Probability that at least 1 of the 3 bridge hands is void of clubs given… [closed]

A bridge hand is dealt so each of 4 players has 13 cards from the 52 card deck. You have 8 clubs in your hand. What is the probability that at least one of the other three hands is void in clubs?
0
votes
1answer
40 views

Decorate Tables

You have $r$ red, $g$ green and $b$ blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons attached to some table shouldn't have the same color. What ...
0
votes
0answers
18 views

Combinatoric task with piggy-bank

Every day king puts either 1p or 2p into a piggy-bank and the total is m pence after n days. Show that for any integer k with 0 <= k <= 2n-m there will have been a period of consecutive days ...
0
votes
0answers
29 views

Modified Graph Coloring Problem

Imagine I have a graph that I'm trying to color with two colors, white and black, except unlike the normal graph coloring problem where you say no two vertices of the same color can be adjacent, I ...
0
votes
1answer
38 views

Finding next permutation of a number.

I need to code some problem and I need help permutating the numbers. The problem is: Given a permutation of the numbers $1,2,3,\ldots,n$ e.g. $n=5$ and permutation is $43251$. I need to find the ...
2
votes
1answer
77 views

Number of possible permutations of n1 1's, n2 2's, n3 3's, n4 4's such that no two adjacent elements are same?

Given n1 number of 1's, n2 number of 2's, n3 number of 3's, n4 number of 4's. form a sequence using all these numbers such that two adjacent numbers should not be same. I have tries lot of things ...
0
votes
0answers
21 views

Sum of two sets with combination

I'm a beginner in mathematics, so, I may be confusing with the vectors... Is there a name and definite operator for this operation ? Two sets A and B : $$A = \{ a_0, a_1 \} \\ B = \{ b_0, b_1, b_2 ...
0
votes
1answer
17 views

number of functions from one set to the other

Let $f:\{0,1,2\}→\{1,2,3,4,5,6,7\}$ be a function such that for every $i, \, j\in {\{0,1,2\}}$ where $i<j$, we have $f(i)<f(j)$. How many such functions can we have? Taking different cases for ...
1
vote
3answers
36 views

Probability of drawing certain hand, incorrect answer, but why? [duplicate]

So I am drawing $5$ cards from a standard deck of $52%$ I want to find the probability that I draw $5$ consecutive cards of same suit with no card looping, and the ace is card $1$. So the ...
2
votes
2answers
26 views

Counting Number of Possibilities using Inclusion-Exclusion

I have been tasked with answering the following combinatorics problem for a homework assignment: Consider the set of all six digit numbers that don’t begin with 0. How many of these have at least one ...
1
vote
0answers
22 views

How many Mad Libs combinations will result when requiring a particular distance between sentences?

You are randomly filling in a Mad Libs type sentence with words from a set of dictionaries. For instance: Sentence: The [COLOR] [ANIMAL] [VERBED] a [NOUN]. Dictionaries: COLOR: blue white orange ...
1
vote
3answers
53 views

Prove $n^{n+1}$ is greater than $(n+1)^n$ for all $n > 2$

The question of whether $2014^{2015}$ or $2015^{2014}$ is greater came up in my Calculus class and it seems clear that $2014^{2015} > 2015^{2014}$ based on a table comparing the sequences $s_n = ...
1
vote
0answers
17 views

How can you tile this checkerboard with trominoes? [duplicate]

Ok, so define a tromino as a $1$x$3$ tile. If a corner is removed from an $8$x$8$ board, is it possible to tile it with these trominoes? So far, I have concluded that you would need $21$ trominoes to ...
1
vote
1answer
43 views

Counting Problems

a) A set of eight tiles can be arranged to form the word SATURDAY. How many three-letter “words” can be formed with these tiles if no tile is to be used more than once? I did $8\cdot 7\cdot 6$ but ...
1
vote
0answers
71 views

Calculating the probability of letter assignment

We have 10 letters written to 10 different friends and the 10 addressed envelops. The letters are put into the envelops at random, that is, all 10! assignment are equally likely. (a) What is the ...
2
votes
1answer
29 views

How many ways to place n distingusishable balls into m distinguishable bins of size s?

Let there be $n$ distinguishable balls and $m$ distinguishable bins, each bin of size $s$, that is, we cannot place more than $s$ balls into it. How many possibilites are there to place the balls into ...
0
votes
1answer
16 views

Finding a seating arrangement of $4$ different people in $n$ rounds

I have a practical problem. I want to arrange a speeddate event with $24$ or $32$ people in $7$ rounds. I have a room with sufficiently many tables and I want $4$ people per table and each round must ...
1
vote
0answers
40 views

Counting the number of partitions having blocks of cardinality 2 and non-distinct elements

Say I have a set of integers $\{1,2,\cdots,n\}$, then there exists $B_n$ partitions of this set where $B_n$ is a Bell number. For instance, there are $B_3$=5 partitions of the set $\{1,2,3\}$: $$ ...
1
vote
0answers
25 views

Upper bound on number of ways to place $n$ indistinguishable objects into $k$ distinguishable intervals of size $s$

I need a simple, but tight upper bound on the number of ways to distribute some $n$ indistinguishable objects among $k$ distinguishable boxes of size $s$. The formula for this quantity is absolutely ...
-1
votes
0answers
12 views

Birkhoff polytope (diameter is $2$)

I did not understand the proof of the following proposition: Prop. $2.29$: Diameter of birkhoff polytope is $2$. This is the link.
0
votes
0answers
11 views

Hyperplane arrangements and matroids

I'm studying some topics related to hyperplane arrangements and matroids. I've some problem in finding some practical example. Here's my question: Let $\mathbb{K}$ be a field (suppose of ...
0
votes
1answer
61 views

How many 6 digit numbers with 2 or 3 repetitions allowed

Solution is pretty well known for the question: how many $6$ digit numbers can be written by using digits $0,..,9$, where, every digit can be used only once. However, while I was thinking today, I ...
3
votes
1answer
49 views

Combinatorics in chess

Let $ ABCD \ $ be an finite chessboard ($n*n$ tiles) where $A$ is the left lower corner and $C$ its opposite. Each tile is denoted by a square with length $L=1$. Our purpose is to determine the ...
0
votes
1answer
13 views

Problem finding $10$-combinations of multisets

Today I had my exam of discrete maths and was asked to find the: no. of $10$-combinations of multiset $\{\infty a,3b,6c\}$. What I did was that: consider set $A_1=$ no. of ways such that no ...
0
votes
0answers
33 views

Number of solutions to equation

I need to find the number of possible solutions to the equation x1+x2+x3+x4=9 where x1,x2,x3,x4 are natural numbers (including 0) and none of them are equal to 4 or 5. Checking with this: ...
3
votes
2answers
33 views

Partitions without 2

How do I find the generating function for partitions of $n$ that have no part with size $2$? In general, how would I find this for partitions that have no part of size $k$?
1
vote
0answers
44 views

Filling a square table with numbers

Suppose we have integers from $1$ to $q$ and a square table of $p$ rows. Let $q \leq p^2$. Denote $C_i$ to be $i$-th column of the table. The table is filled with numbers from $1$ to $q$ in such way ...
2
votes
2answers
50 views

The smallest $n$ for which the sum of binomial coefficients exceeds $31$

I have a problem with the binomial theorem. What is the result of solving this inequality: $$ \binom{n}{1} + \binom{n}{2} + \binom{n}{3} + \cdots +\binom{n}{n} > 31 $$
2
votes
1answer
47 views

Number of unlabeled simple graphs with $n$ nodes even for all $ n\ge 5$?

The extended version of OEIS for the number of unlabeled simple graphs with $n$ nodes shows that the only odd number (besides the trivial cases $n = 0 $ and $n = 1$) is for $n=4$ ($11$ graphs). The ...
1
vote
0answers
49 views

n bins, m balls and m>n: Probability of at least r bin containing exactly k balls.When bins are numeret from 1…n and ball is equale.

I want to calculate this probability .In this question $N$ bins, $m$ balls: Probability of any bin containing *exactly* $k$ balls. calculate this but I can not understand this calculation.To be more ...
0
votes
2answers
27 views

I am kind of confused on how to solve this question. Can anyone help please

If we let $S$ be the set that is defined by the following two rules: 1 is an element of the set $s$ If $s$ is an element of the set $s$, then x+$2 \sqrt{x}+1$ is also an element of the set $s$ how ...
-1
votes
1answer
36 views

Prove that exists such sequence…

Given is a set of number: $$ {a_1, ... , a_{11} } $$ Prove that there exists a sequence of non-zero, that $$ x_1, ..., x_ {11} $$ of words from the set {1,0,1} that the number of: $$ x_1a_1 + ... + ...
0
votes
1answer
92 views

COmbinatoric : Guess who is the winner candidate?

National Radio Broadcast will put a contest to guess five winners out of twelve local boxers who will compete to win the best 5 boxers. All twelve boxers are equally good so the chance of winning is ...
0
votes
0answers
26 views

Number of matrices based on Hamming distance

Given a set $S$ of all possible binary matrices of order $n\times2^n$ where $n\in N$. We can name the matrices as $M_i$ where i is the decimal representation of the binary string of length $n\cdot ...
0
votes
2answers
35 views

Ball Occupancy Problem

Suppose we put r balls at random in n boxes, i.e., all n r assignments of balls to boxes have equal probability. Let Ai be the event that the ith box is empty and Nn = the number of empty boxes. It is ...
0
votes
1answer
15 views

How many 4-digit integers greater than zero have 3 or 6 as their third digit and 3 as their first digit?

Questions like these are very common on PSAT and SAT tests, and I can never figure it out within a suitable amount of time. Is there an easier way to work through these kinds of problems without ...
1
vote
3answers
84 views

Permutations and Combinations? 3 digit number…

1) Make a 3 digit even number without repeated digits, using 0, 4, 5 , 6, 7. Also the first digit cannot be 0. 2)Arrange 12 books in a line, 4 of which are english, 3 of which are science, and 5 ...