# Tagged Questions

18 views

### How many binary strings are there of length n with k ones? [closed]

For some fixed $n$, how many binary strings are there with $k$ $1$s and $n-k$ $0$s (where $n>k$)?
58 views

### Count 1-bit in binary integers

Given an integer range [A,B], (1) What’s the probability to get a 1-bit if we first randomly choose a number x in the range and then randomly choose a bit from x? (2) What’s the expected number of ...
109 views

### Combinatorics: Binary Strings

Are the these 2 binary generation expressions equal? If so, how do I simplify my answer to match the solution's? Question: The set of binary strings where the length of each block of 0s is divisible ...
81 views

### Product of “reversed” numbers

Consider any 2 binary numbers, e.g.: 10101011 ; 11111101 and their product, say P. "Reverse" (mirror image) all the digits of the 2 numbers, e.g.: ...
52 views

### Probability of sum over a window of binary vector

I have a vector of one's and zero's of length n with a probability p of observing a one and 1-p of observing a zero. I slide a (overlapping) window of size $k$ across this vector and take the sum ...
35 views

### My Proof for the Cardinality of a Particular Binary Distribution

my question reads as follows: I have constructed a proof and am concerned about 2 things: 1) The validity of my proof. 2) The construction of my proof. I am asking for someone to read through ...
56 views

### How many ways are there to arrange 1's and 0's with no two 1's in a row? [duplicate]

Given n spaces, how many ways are there to fill up the spaces with 1's and 0's such that no two 1's are together. For example, let's say n = 3 (_ _ _). There are 5 ways to fill up the spaces such ...
22 views

### Partioning Mystery

Who has the wisdom to answer the following: 9 distinct marbles distrubted into 4 distinct bags with each bag receiving at least 1 marble,how many ways can this be done? Thankyou for contributing! ...
356 views

### Formula for binary sequences of length m with no n consecutive 1s?

Formula for binary sequences of length $m$ with no $n$ consecutive $1$s? I know The number of binary strings of length $m$ without consecutive $1$s is the Fibonacci number $F_{m+2}$. But how about ...
61 views

### Number of 'unique' one bit binary functions with N-bit inputs

Consider the set of binary functions that takes an N-bit input -> 1 bit output. There are 2^(2^N) elements in this set. Now potentially reduce this set by restricting to only considering functions ...
72 views

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving ...
273 views

### Generating Function for Binary String Question

The following is an assignment question I have been trying to work out for quite some time. Let $C(x,y)=\sum_{n,k \geq 0} c_{n,k} x^{n} y^{k}$, where $c_{n,k}$ is the number of binary strings of ...
439 views

### Binary string with even and odd number of 1s [duplicate]

How could it be shown that the number of binary string of length k with an even number of 1s is the same as those with an odd number of 1s. Eg. for $k = 3$ : Binary string length 3 with even amount ...
107 views

### Binary multiplication

Please don't be to harsh with me if you think that this is to simple, I just don't understand it. I been trying to follow this site(Method 2) to solve simple multiplication of $3 * 3 = 9$, but it ...
149 views

### Finite bit strings that do not contain '$00$'

I am studying for an exam and I am having trouble with this practice question: In this question, we consider finite bit strings that do not contain $00$. Examples of such bitstrings are $0101010101$ ...
219 views

107 views

### Matrix + combinatorial or conditional probability: bit patterns

I'm trying to get my head around a problem, and it's not working. The problem: consider an NxN matrix that represents a binary number. For instance, a 4x4 matrix is a 16 bit number, a 6x6 matrix is ...
97 views

### number of binary sets - combinatorics

Just ran into this question: let $f(n,m)$ be the number of binary strings where there are at most $n$ 1's and at most $m$ 0's. the empty string also counts as a string. show that ...
251 views

### An odd question about induction.

Given $n$ $0$'s and $n$ $1$'s distributed in any manner whatsoever around a circle, show, using induction on $n$, that it is possible to start at some number and proceed clockwise around the circle to ...
290 views

### Quick question about binary strings

Determine the unambigious expression which generates every string in this set. The set of all binary strings which contains 001111 as a substring. I am thinking that the answer should be ...
167 views

### Recursive equation for palindromes

Can someone help me determine the recursive equation for all binary strings that are palindromes? A binary string is a palindrome if it reads the same forward and backward. Examples of palindromes are ...
94 views

### Find the generating function for this set of strings

Let $a(n)$ be the number of $\{0,1\}$-strings of length $n$ which contain no $4$ consecutive $1$'s and no $4$ consecutive $0$'s (don't contain "$0000$" or "$1111$"). Find the generating function for ...
170 views

### Unambiguous expression for binary strings containing some substring

Is there some systematic way for finding an unambiguous expression for a binary string which contains a certain substring? For finding expressions not containing a substring, it is sometimes easy to ...
138 views

### Binary Strings Question

prove that the following expression for a set of binary strings S is ambigious S = {101,1101,1011}* Thanks for all your help!
244 views

### Closed formula to count number of binary numbers of length $x$ having at least $y$ $1$ bits

I'm interested in solving a sub problem of the algorithm related question from SO How many binary numbers having given constraints .... The sub problem being, having $x \geq y$ determine how many ...
102 views

### Combinatorics based binary sequence

We all know the standard base 2 representation of integers and many of you will know of Gray codes. Does anybody know of a name (or something I can use to find a good reference) for a method of ...
156 views

### Determining the position of a binary value with $k$ one bits and $n-k$ zeros in an enumeration of $C_k^n$ bit strings

I first enumerate a list of all possible binary strings for a length $n$ (e.g., ["00", "01", "10", "11"] for $n=4$). This leads to a list of $2^n$ binary strings. Within that list of $2^n$ elements, ...
344 views

### Multiply two large numbers in under 1000 instructions using reduced ISA with only 7 registers [closed]

Is it possible to multiply two large (15 bit) numbers efficiently (in under 1000 instructions) using the following ISA: ...
237 views

815 views

### Count the number of n-bit strings with an even number of zeros.

I am currently self-studying introductory combinatorics by reading Introduction to combinatorial mathematics. I am currently in the first chapter, and I have a question regarding one of the examples. ...
64 views

### q-ary code/Latin squares

For any value of $q$ the largest number of elements in any q-ary code $C$ of length $4$, distance $3$ is $q^2$. How can we prove that this is attainable iff there are a pair of mutually orthogonal ...
165 views

### Number 1s in a binary grid

Consider a binary grid of size 4*4, each of cell can either have 0 or 1. Among all possible 2^16 arrangement how many arrangement of such grid exist in which each row and column contains even number ...
Whilst solving a question, I have come across a problem regarding the maximal number of possible distinct $k$-length binary sub-strings in an $n$-length binary string. My thought process was that if ...